{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Partition String Into Substrings With Values at Most K"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumPartition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将字符串分割成值不超过 K 的子字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串&nbsp;<code>s</code>&nbsp;，它每一位都是&nbsp;<code>1</code>&nbsp;到&nbsp;<code>9</code>&nbsp;之间的数字组成，同时给你一个整数&nbsp;<code>k</code>&nbsp;。</p>\n",
    "\n",
    "<p>如果一个字符串 <code>s</code>&nbsp;的分割满足以下条件，我们称它是一个 <strong>好</strong>&nbsp;分割：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>s</code>&nbsp;中每个数位 <strong>恰好</strong>&nbsp;属于一个子字符串。</li>\n",
    "\t<li>每个子字符串的值都小于等于&nbsp;<code>k</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回 <code>s</code>&nbsp;所有的 <strong>好</strong>&nbsp;分割中，子字符串的&nbsp;<strong>最少</strong>&nbsp;数目。如果不存在 <code>s</code>&nbsp;的<strong>&nbsp;好</strong>&nbsp;分割，返回&nbsp;<code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p><b>注意：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>一个字符串的 <strong>值</strong>&nbsp;是这个字符串对应的整数。比方说，<code>\"123\"</code>&nbsp;的值为&nbsp;<code>123</code>&nbsp;，<code>\"1\"</code>&nbsp;的值是&nbsp;<code>1</code>&nbsp;。</li>\n",
    "\t<li><strong>子字符串</strong>&nbsp;是字符串中一段连续的字符序列。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"165462\", k = 60\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>我们将字符串分割成子字符串 \"16\" ，\"54\" ，\"6\" 和 \"2\" 。每个子字符串的值都小于等于 k = 60 。\n",
    "不存在小于 4 个子字符串的好分割。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"238182\", k = 5\n",
    "<b>输出：</b>-1\n",
    "<strong>解释：</strong>这个字符串不存在好分割。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s[i]</code>&nbsp;是&nbsp;<code>'1'</code>&nbsp;到&nbsp;<code>'9'</code>&nbsp;之间的数字。</li>\n",
    "\t<li><code>1 &lt;= k &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [partition-string-into-substrings-with-values-at-most-k](https://leetcode.cn/problems/partition-string-into-substrings-with-values-at-most-k/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [partition-string-into-substrings-with-values-at-most-k](https://leetcode.cn/problems/partition-string-into-substrings-with-values-at-most-k/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"165462\"\\n60', '\"238182\"\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        \n",
    "        n = len(s)\n",
    "        \n",
    "        if k < max(int(x) for x in s):\n",
    "            return -1\n",
    "        \n",
    "        ans = 1\n",
    "        tmp = \"\"\n",
    "        for j in range(n):\n",
    "            if int(tmp + s[j]) <= k:\n",
    "                tmp += s[j]\n",
    "            else:\n",
    "                ans += 1\n",
    "                tmp = s[j]\n",
    "        \n",
    "        return ans\n",
    "                \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ans, x = 1, 0\n",
    "        for v in map(int, s):\n",
    "            if v > k: return -1\n",
    "            x = x * 10 + v\n",
    "            if x > k:\n",
    "                ans += 1\n",
    "                x = v\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        if int(max(s)) > k:\n",
    "            return -1\n",
    "\n",
    "        ans = cnt = 0\n",
    "        for i in map(int, s):\n",
    "            next = cnt * 10 + i\n",
    "            if next <= k:\n",
    "                cnt = next\n",
    "            else:\n",
    "                cnt = i\n",
    "                ans += 1\n",
    "        return ans + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ans, x = 1, 0\n",
    "        for v in map(int, s):\n",
    "            if v > k: return -1\n",
    "            x = x * 10 + v\n",
    "            if x > k:\n",
    "                ans += 1\n",
    "                x = v\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ans,x = 1,0\n",
    "        for v in map(int,s):\n",
    "            if v>k:return -1\n",
    "            x = x*10+v\n",
    "            if x>k:\n",
    "                ans+=1\n",
    "                x =v\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        res = 1\n",
    "        x = 0\n",
    "        for v in map(int, s):\n",
    "            if v>k:\n",
    "                return -1\n",
    "            x = x * 10 +v\n",
    "            if x>k:\n",
    "                res += 1\n",
    "                x = v\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            ret = inf\n",
    "            for j in range(i-1, -1, -1):\n",
    "                if int(s[j: i]) > k:\n",
    "                    break\n",
    "                ret = min(ret, dfs(j) + 1)\n",
    "            return ret\n",
    "        ret = dfs(len(s))\n",
    "        return ret if ret < inf else -1\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        dp = [0] + [inf] * n\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if int(s[j: i]) > k:\n",
    "                    break\n",
    "                dp[i] = min(dp[i], dp[j] + 1)\n",
    "        print(dp)\n",
    "        return dp[-1] if dp[-1] < inf else -1\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ret, tmp = 1, 0\n",
    "        for x in map(int, s):\n",
    "            if x > k: return -1\n",
    "            tmp = tmp * 10 + x\n",
    "            if tmp > k:\n",
    "                tmp = x\n",
    "                ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ans, x = 1, 0\n",
    "        s = s[::-1]\n",
    "        t = 0\n",
    "        for v in map(int, s):\n",
    "            if v > k: return -1\n",
    "            x = x + (10**t) * v\n",
    "            t += 1\n",
    "            if x > k:\n",
    "                ans += 1\n",
    "                x = v\n",
    "                t = 1 \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ans = 1\n",
    "        t = 0\n",
    "        for x in map(int, s):\n",
    "            if x > k: return -1\n",
    "            t = t * 10 + x\n",
    "            if t > k:\n",
    "                ans += 1\n",
    "                t = x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ans, x = 1, 0\n",
    "        for v in map(int, s):\n",
    "            if v > k: return -1\n",
    "            x = x * 10 + v\n",
    "            if x > k:\n",
    "                ans += 1\n",
    "                x = v\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        if int(max(s)) > k:\n",
    "            return -1\n",
    "\n",
    "        ans = cnt = 0\n",
    "        for i in map(int, s):\n",
    "            next = cnt * 10 + i\n",
    "            if next <= k:\n",
    "                cnt = next\n",
    "            else:\n",
    "                cnt = i\n",
    "                ans += 1\n",
    "        return ans + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        for i in s:\n",
    "            if int(i)>k:\n",
    "                return -1\n",
    "        n=len(s)\n",
    "        l=0;r=0\n",
    "        res=1\n",
    "        while r<n and int(s[l:r+1])<=k:\n",
    "            r+=1\n",
    "            if int(s[l:r+1])>k:\n",
    "                l=r\n",
    "                res+=1\n",
    "        return res\n",
    "                        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ans, x = 1, 0\n",
    "        for v in map(int, s):\n",
    "            if v > k: return -1\n",
    "            x = x * 10 + v\n",
    "            if x > k:\n",
    "                ans += 1\n",
    "                x = v\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        if k <= 8:\n",
    "            for ss in s:\n",
    "                if int(ss) > k:\n",
    "                    return -1\n",
    "            \n",
    "            return len(s)\n",
    "\n",
    "\n",
    "        val = 0\n",
    "        i = 0\n",
    "        cnt = 0\n",
    "        while i < len(s):\n",
    "            # val *= 10 \n",
    "            # val += int(s[i]) \n",
    "            while i < len(s) and val * 10 + int(s[i]) <= k:\n",
    "                val = val * 10 + int(s[i])\n",
    "                i += 1\n",
    "\n",
    "            cnt += 1\n",
    "            val = 0\n",
    "\n",
    "        return cnt\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "        # left = 1\n",
    "        # right = len(s)\n",
    "\n",
    "        # while left < right:\n",
    "        #     mid = left + (right - left) // 2\n",
    "\n",
    "        #     if check(mid):\n",
    "        #         right = mid\n",
    "        #     else:\n",
    "        #         left = mid + 1\n",
    "        \n",
    "        # return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, ss: str, k: int) -> int:\n",
    "        ans = 0\n",
    "        s = 0\n",
    "        for c in ss:\n",
    "            if s * 10 + int(c) <= k:\n",
    "                s = s * 10 + int(c)\n",
    "            elif int(c) > k:\n",
    "                return -1\n",
    "            else:\n",
    "                s = int(c)\n",
    "                ans += 1\n",
    "        return ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        v = int(s[0])\n",
    "        ans = 1\n",
    "        for i in range(1, n):\n",
    "            if v * 10 + int(s[i]) >= k:\n",
    "                ans += 1\n",
    "                v = 0\n",
    "            v = v * 10 + int(s[i])\n",
    "            if v > k: return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ans = 1\n",
    "        pre = 0\n",
    "        for i in s:\n",
    "            tmp = int(i)\n",
    "            if tmp > k:\n",
    "                return -1\n",
    "            pre = 10 * pre + tmp\n",
    "            if pre > k:\n",
    "                ans += 1\n",
    "                pre = tmp\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        # 先解决特例\n",
    "        if k < 10:\n",
    "            for ch in s:\n",
    "                if int(ch) > k:\n",
    "                    return -1\n",
    "            return len(s)\n",
    "        \n",
    "        ans = 0\n",
    "        left = 0\n",
    "        for right, _ in enumerate(s):\n",
    "            if right > left and int(s[left: right]) > k:\n",
    "                ans += 1\n",
    "                left = right - 1\n",
    "        ans += 2 if int(s[left: len(s)]) > k else 1 \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        i = 0\n",
    "        res = 0\n",
    "        while i < len(s):\n",
    "            if int(s[i]) > k:\n",
    "                return -1\n",
    "                \n",
    "            j = i\n",
    "            while j < len(s) and int(s[i:j+1]) <= k:\n",
    "                j += 1\n",
    "            res += 1\n",
    "            i = j\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ans = 1\n",
    "        n = len(s)\n",
    "        x = 0\n",
    "        \n",
    "        for v in map(int,s):\n",
    "            if v > k:\n",
    "                return -1\n",
    "            x = x * 10 + v\n",
    "            if x > k:\n",
    "                ans += 1\n",
    "                x = v\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        if k < 10:\n",
    "            if int(max(list(s))) > k:\n",
    "                return -1\n",
    "            else:\n",
    "                return len(s)\n",
    "        else:\n",
    "            cnt = 0\n",
    "            p = 0\n",
    "            now = 0\n",
    "            while p < len(s):\n",
    "                while p < len(s) and now * 10 + int(s[p]) <= k:\n",
    "                    now = now * 10 + int(s[p])\n",
    "                    p += 1\n",
    "                \n",
    "                cnt += 1\n",
    "                now = 0\n",
    "            \n",
    "            return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ans, x = 1, 0\n",
    "        for v in map(int, s):\n",
    "            if v > k: return -1\n",
    "            x = x * 10 + v\n",
    "            if x > k:\n",
    "                ans += 1\n",
    "                x = v\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        curr, ans = 0, 1\n",
    "        for d in s:\n",
    "            if int(d) > k:\n",
    "                return -1\n",
    "            curr = 10 * curr + int(d)\n",
    "            if curr > k:\n",
    "                ans += 1\n",
    "                curr = int(d)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        x=0\n",
    "        ans=1\n",
    "        for i in map(int,s):\n",
    "            if i > k:\n",
    "                return -1\n",
    "            x=x*10+ i \n",
    "            if x>k:\n",
    "                ans=ans+1\n",
    "                x=i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ans = 1\n",
    "        x = 0\n",
    "        for c in s:\n",
    "            v = int(c)\n",
    "            if v > k : return -1\n",
    "            x = x *10 + v\n",
    "            if x > k:\n",
    "                ans += 1\n",
    "                x = v\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        v = ord(s[0]) - ord('0')\n",
    "        ans = 1\n",
    "        for i in range(1, n):\n",
    "            if v * 10 + ord(s[i]) - ord('0') >= k:\n",
    "                ans += 1\n",
    "                v = 0\n",
    "            v = v * 10 + ord(s[i]) - ord('0')\n",
    "            if v > k: return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ans, x = 1, 0\n",
    "        for v in map(int, s):\n",
    "            if v > k: return -1\n",
    "            x = x * 10 + v\n",
    "            if x > k:\n",
    "                ans += 1\n",
    "                x = v\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 方法2：贪心\n",
    "# 思考：第一个字符串应该划分在哪？\n",
    "# 如果给后面留下的字符串越短，答案显然不会变大，因此第一个字符串越长越好。 \n",
    "           \n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:         \n",
    "        ans = 1\n",
    "        x = 0\n",
    "        for v in map(int, s):  # s = \"165462\", k = 60\n",
    "            if v > k:\n",
    "                return -1\n",
    "            x = x * 10 + v\n",
    "            if x > k:\n",
    "                ans += 1\n",
    "                x = v\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "\n",
    "        p = 0\n",
    "        curr = 0\n",
    "        flag = False\n",
    "\n",
    "        while p < n:\n",
    "            curr = curr * 10 + ord(s[p]) - ord('0')\n",
    "\n",
    "            if curr <= k:\n",
    "                flag = True\n",
    "                p += 1\n",
    "            else:\n",
    "                if not flag:\n",
    "                    return -1\n",
    "                ans += 1\n",
    "                curr = 0\n",
    "                flag = False\n",
    "\n",
    "        return ans + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        x = 0\n",
    "        res = 1\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            cur = int(s[i])\n",
    "            if cur > k:\n",
    "                return -1\n",
    "\n",
    "            x = x*10 + cur\n",
    "\n",
    "            if x > k:\n",
    "                res += 1\n",
    "                x = cur\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        x = 0\n",
    "        r = 1\n",
    "        for i in map(int,s):\n",
    "            if i>k:\n",
    "                return -1\n",
    "            x = x*10 + i\n",
    "            if x>k:\n",
    "                x=i\n",
    "                r+=1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        if ord(max(s))-ord('0')>k:\n",
    "            return -1\n",
    "        n=len(s)\n",
    "        ans=0\n",
    "        c=0\n",
    "        for i in range(n):\n",
    "            c=c*10+ord(s[i])-ord('0')\n",
    "            if c>k:\n",
    "                c=ord(s[i])-ord('0')\n",
    "                ans+=1\n",
    "        return ans+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        res = 0\n",
    "        n = len(s)\n",
    "        n1 = len(str(k))\n",
    "        i = 0\n",
    "        if n1 == 1:\n",
    "            res = 0\n",
    "            for c in s:\n",
    "                if c <= str(k):\n",
    "                    res += 1\n",
    "                else:\n",
    "                    return -1\n",
    "            return res\n",
    "        while i < n:\n",
    "            res += 1\n",
    "            if s[i:i+n1] <= str(k):\n",
    "                i += n1\n",
    "            else:\n",
    "                i += n1 -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ans, x = 1, 0\n",
    "        for v in map(int, s):\n",
    "            if v > k: return -1\n",
    "            x = x * 10 + v\n",
    "            if x > k:\n",
    "                ans += 1\n",
    "                x = v\n",
    "        return ans\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ans, x = 1, 0\n",
    "        for v in map(int, s):\n",
    "            if v > k:\n",
    "                return -1\n",
    "            x = x * 10 + v\n",
    "            if x > k:\n",
    "                ans += 1\n",
    "                x = v\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        if not all(int(x)<=k for x in s):\n",
    "            return -1\n",
    "        l = len(str(k))\n",
    "        n = len(s)\n",
    "        v, ans = 0,1\n",
    "        for x in (int(c) for c in s):\n",
    "            v = v*10 + x\n",
    "            if v > k:\n",
    "                ans += 1\n",
    "                v = x\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ans, x = 1, 0 \n",
    "        for v in map(int,s):\n",
    "            if v > k:\n",
    "                return -1\n",
    "            x  = x*10 + v\n",
    "            if x>k:\n",
    "                ans += 1\n",
    "                x = v\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ans, x = 1, 0\n",
    "        for v in map(int, s):\n",
    "            if v > k: return -1\n",
    "            x = x * 10 + v\n",
    "            if x > k:\n",
    "                ans += 1\n",
    "                x = v\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ans , x = 1, 0\n",
    "        for i in map(int,s):\n",
    "            if i>k: return -1\n",
    "            x = x * 10 + i\n",
    "            if x > k:\n",
    "                ans += 1\n",
    "                x = i\n",
    "                continue\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        temp = 0\n",
    "        while left < len(s):\n",
    "            if int(s[left]) > k: return -1\n",
    "            temp = temp * 10 + int(s[left])\n",
    "            if temp > k:\n",
    "                ans += 1\n",
    "                temp = int(s[left])\n",
    "            left += 1\n",
    "        return ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ans = 0\n",
    "        tmp = 0\n",
    "        for x in s:\n",
    "            if int(x) > k:\n",
    "                    return -1\n",
    "            if tmp * 10 + int(x) > k:\n",
    "                # print(tmp)\n",
    "                tmp = int(x)\n",
    "                ans += 1\n",
    "            else:\n",
    "                tmp = tmp * 10 + int(x)\n",
    "        # print(tmp)\n",
    "        if tmp != 0:\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        curr, ans = 0, 1\n",
    "        for d in s:\n",
    "            if int(d) > k:\n",
    "                return -1\n",
    "            curr = 10 * curr + int(d)\n",
    "            if curr > k:\n",
    "                ans += 1\n",
    "                curr = int(d)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ans=0\n",
    "        n=len(s)\n",
    "        temp=0\n",
    "        for i in range(n):\n",
    "            if int(s[i])>k:return -1\n",
    "            if temp*10+int(s[i])<=k:\n",
    "                temp=temp*10+int(s[i])\n",
    "            else:\n",
    "                ans+=1\n",
    "                temp=int(s[i])\n",
    "        \n",
    "        \n",
    "        \n",
    "        return ans+1\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        if not all(int(x)<=k for x in s):\n",
    "            return -1\n",
    "        l = len(str(k))\n",
    "        n = len(s)\n",
    "        left, ans = 0,1\n",
    "        for right in range(n):\n",
    "            if int(s[left:right+1]) > k:\n",
    "                ans += 1\n",
    "                left = right\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ls = len(s)\n",
    "        if k < 10:\n",
    "            return ls if all(ch <= str(k) for ch in s) else -1\n",
    "        k = str(k)\n",
    "        lk = len(k)\n",
    "\n",
    "        # 贪心法\n",
    "        i = ans = 0\n",
    "        while i < ls:\n",
    "            cur = s[i:i+lk]\n",
    "            i += lk if cur <= k or len(cur) < lk else lk - 1\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ans , x = 1, 0\n",
    "        for i in map(int,s):\n",
    "            if i>k: return -1\n",
    "            x = x * 10 + i\n",
    "            if x > k:\n",
    "                ans += 1\n",
    "                x = i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        str_k = str(k)\n",
    "        k_len = len(str_k)\n",
    "        l,r = 0,0\n",
    "        while l<=n-1:\n",
    "            r = min(l+k_len-1, n-1)\n",
    "            if int(s[l:r+1])<=k:\n",
    "                res+=1\n",
    "                l = r+1\n",
    "            else:\n",
    "                if l==r: return -1\n",
    "                res+=1\n",
    "                l = r\n",
    "            pass\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ans = 0\n",
    "        num = 0\n",
    "        for ch in s:\n",
    "            if int(ch) > k:\n",
    "                return -1\n",
    "            if num * 10 + int(ch) > k:\n",
    "                ans += 1\n",
    "                num = int(ch)\n",
    "            else:\n",
    "                num = num * 10 + int(ch)\n",
    "            \n",
    "\n",
    "        return ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ans, x = 1, 0\n",
    "        for v in map(int, s):\n",
    "            if v > k: return -1\n",
    "            x = x * 10 + v\n",
    "            if x > k:\n",
    "                ans += 1\n",
    "                x = v\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ans, x = 1, 0\n",
    "        for v in map(int, s):\n",
    "            if v > k: return -1\n",
    "            x = x * 10 + v\n",
    "            if x > k:\n",
    "                ans += 1\n",
    "                x = v\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        if k <= 8:\n",
    "            for ss in s:\n",
    "                if int(ss) > k:\n",
    "                    return -1\n",
    "            \n",
    "            return len(s)\n",
    "\n",
    "\n",
    "        def check(tar):\n",
    "            val = 0\n",
    "            i = 0\n",
    "            cnt = 0\n",
    "            while i < len(s):\n",
    "                # val *= 10 \n",
    "                # val += int(s[i]) \n",
    "                while i < len(s) and val * 10 + int(s[i]) <= k:\n",
    "                    val = val * 10 + int(s[i])\n",
    "                    i += 1\n",
    "\n",
    "                cnt += 1\n",
    "                val = 0\n",
    "\n",
    "            return cnt <= tar\n",
    "                \n",
    "\n",
    "\n",
    "        left = 1\n",
    "        right = len(s)\n",
    "\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ans, x = 1, 0\n",
    "        for v in map(int, s):\n",
    "            if v > k:\n",
    "                return -1\n",
    "            x = x * 10 + v\n",
    "            if x > k:\n",
    "                ans += 1\n",
    "                x = v\n",
    "        return ans\n",
    "\n",
    "        # ans = 0\n",
    "        # num = 0\n",
    "        # for ch in s:\n",
    "        #     if int(ch) > k:\n",
    "        #         return -1\n",
    "        #     if num * 10 + int(ch) > k:\n",
    "        #         ans += 1\n",
    "        #         num = int(ch)\n",
    "        #     else:\n",
    "        #         num = num * 10 + int(ch)\n",
    "\n",
    "        # return ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        if k<10:\n",
    "            for i in s:\n",
    "                if int(i)>k:\n",
    "                    return -1\n",
    "        m=len(str(k))\n",
    "        i=0\n",
    "        ans=0\n",
    "        while i<len(s):\n",
    "            print(i+m,end=' ')\n",
    "            print(len(s))\n",
    "            if i+m<=len(s):\n",
    "                print(s[i:i+m])\n",
    "                if int(s[i:i+m])<=k:\n",
    "                    i+=m\n",
    "                else:\n",
    "                    i+=m-1\n",
    "                ans+=1\n",
    "            else:\n",
    "                ans+=1\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        s = [int(x) for x in s]\n",
    "        if k < 10 and max(s) > k:\n",
    "            return -1\n",
    "        l_k = len(str(k))\n",
    "        if l_k == 1:\n",
    "            return len(s)\n",
    "\n",
    "        cnt = 0\n",
    "        index = 0\n",
    "        while index+l_k <= len(s):\n",
    "            curr_num_1 = int(''.join([str(x) for x in s[index:index+l_k]]))\n",
    "            if curr_num_1 < k:\n",
    "                index = index+l_k\n",
    "            else:\n",
    "                index = index+l_k-1\n",
    "            cnt += 1\n",
    "        if len(s[index:]) == 0:\n",
    "            return cnt\n",
    "        else:\n",
    "            return cnt+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        # 贪心，前面选择小于等于k的最大索引位置进行分割\n",
    "        arr=list(map(int,s))\n",
    "        if max(arr)>k:\n",
    "            return -1\n",
    "        else:\n",
    "            i,n=0,len(arr)\n",
    "            cnt=0\n",
    "            while i<n:\n",
    "                s=i \n",
    "                num=0\n",
    "                while i<n and 10*num+arr[i]<=k:\n",
    "                    num=10*num+arr[i]\n",
    "                    i+=1\n",
    "                # print(s,i)\n",
    "                cnt+=1\n",
    "            return cnt\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        # 贪心，前面选择小于等于k的最大索引位置进行分割\n",
    "        arr=list(map(int,s))\n",
    "        if max(arr)>k:\n",
    "            return -1\n",
    "        else:\n",
    "            i,n=0,len(arr)\n",
    "            cnt=0\n",
    "            while i<n:\n",
    "                s=i \n",
    "                num=0\n",
    "                while i<n and 10*num+arr[i]<=k:\n",
    "                    num=10*num+arr[i]\n",
    "                    i+=1\n",
    "                # print(s,i)\n",
    "                cnt+=1\n",
    "            return cnt+1 if num>k else cnt \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        i = 1\n",
    "        current = s[0]\n",
    "        res = []\n",
    "        while i < len(s):\n",
    "            if int(current + s[i])<=k:\n",
    "                \n",
    "                current += s[i] \n",
    "                i+=1\n",
    "                continue\n",
    "            else:\n",
    "                if int(current) > k:\n",
    "                    return -1\n",
    "                else:\n",
    "                    res.append(current)\n",
    "\n",
    "                    current = s[i] \n",
    "                    i+=1\n",
    "        if int(current) <= k:\n",
    "            res.append(current)\n",
    "        else:\n",
    "            return -1\n",
    "        print(res)\n",
    "        return len(res)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        f = [float('inf')] * (n + 1)\n",
    "        f[0] = 0\n",
    "        if int(s[0]) <= k:\n",
    "            f[1] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(i, 0, -1):\n",
    "                if int(s[j-1:i]) > k:\n",
    "                    break\n",
    "                f[i] = min(f[i], f[j-1] + 1)\n",
    "        if f[-1] == float('inf'):\n",
    "            return -1\n",
    "        else:\n",
    "            return f[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "使用dp的方法来试着过这道题\n",
    "f[i]表示分割前i个字符所需的最少子串数目\n",
    "for循环枚举分割位置 ,直接倒着枚举更加方便\n",
    "'''\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        f=[inf]*(n+1)\n",
    "        f[0]=0\n",
    "        for i in range(n):\n",
    "            num=0\n",
    "            p=1\n",
    "            for j in range(i,-1,-1):\n",
    "                num+=(ord(s[j])-ord('0'))*p\n",
    "                p*=10\n",
    "                if num>k:break  \n",
    "                f[i+1]=min(f[i+1],f[j]+1)\n",
    "        return f[n] if f[n]<inf else -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        dp = [inf]*(n+1)\n",
    "        dp[0] = 0\n",
    "        m = len(str(k))\n",
    "        for i in range(n):\n",
    "            for j in range(max(i-m, 0), i+1):\n",
    "                if int(s[j:i+1]) <= k and dp[j]+1<dp[i+1]:\n",
    "                    dp[i+1] = dp[j] + 1\n",
    "        return dp[-1] if dp[-1] < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        f=[1000001]*(n+1)\n",
    "        f[0]=1\n",
    "        for i in range(1,n+1):\n",
    "            j=i\n",
    "            while j>0:\n",
    "                cur=int(s[j-1:i])\n",
    "                if cur<=k: f[i]=min(f[i],f[j-1]+1)\n",
    "                else: break\n",
    "                j -=1\n",
    "\n",
    "        return f[n]-1 if f[n]<1000001 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = float('inf')\n",
    "            num = 0\n",
    "            power = 1\n",
    "            for j in range(i, 0, -1):\n",
    "                num += int(s[j - 1]) * power\n",
    "                power *= 10\n",
    "                if num > k:\n",
    "                    break\n",
    "                dp[i] = min(dp[i], dp[j - 1] + 1)\n",
    "        return dp[n] if dp[n] != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = float('inf')\n",
    "            num = 0\n",
    "            power = 0\n",
    "            for j in range(i, 0, -1):\n",
    "                num += int(s[j - 1]) * (10 ** power)\n",
    "                power += 1\n",
    "                if num > k:\n",
    "                    break\n",
    "                dp[i] = min(dp[i], dp[j - 1] + 1)\n",
    "        return dp[n] if dp[n] != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        dp = [float('inf')] * (n + 1)\n",
    "        dp[0] = 0  # 初始化，空字符串不需要任何子字符串\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            val = 0\n",
    "            for j in range(i, 0, -1):  # 从 i 到 1，尝试所有可能的子字符串 s[j:i]\n",
    "                val = val + int(s[j - 1]) * (10 ** (i - j))  # 子字符串 s[j-1:i] 的值\n",
    "                if val > k:\n",
    "                    break  # 如果子字符串的值大于 k，那么没有必要继续尝试\n",
    "                dp[i] = min(dp[i], dp[j - 1] + 1)  # 更新 dp[i]\n",
    "\n",
    "        return dp[-1] if dp[-1] != float('inf') else -1  # 如果找不到好分割，返回 -1\n",
    "\n",
    "# 测试代码\n",
    "sol = Solution()\n",
    "print(sol.minimumPartition(\"1432219\", 5))  # 输出应为 3（子字符串为： \"1\", \"4\", \"3\", \"2\", \"2\", \"1\", \"9\"）\n",
    "print(sol.minimumPartition(\"12345\", 1000))  # 输出应为 1（子字符串为： \"12345\"）\n",
    "print(sol.minimumPartition(\"12345\", 10))  # 输出应为 5（子字符串为： \"1\", \"2\", \"3\", \"4\", \"5\"）\n",
    "print(sol.minimumPartition(\"12345\", 0))  # 输出应为 -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            if(int(s[i]) > k):\n",
    "                return -1\n",
    "        dp = list(range(n+1))\n",
    "        for i in range(n):\n",
    "            for j in range(i,-1,-1):\n",
    "                if(int(s[j:i+1]) > k):\n",
    "                    break\n",
    "                dp[i+1] = min(dp[i+1], dp[j] + 1)\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            ret = inf\n",
    "            for j in range(i-1, -1, -1):\n",
    "                if int(s[j: i]) > k:\n",
    "                    break\n",
    "                ret = min(ret, dfs(j) + 1)\n",
    "            return ret\n",
    "        ret = dfs(len(s))\n",
    "        return ret if ret < inf else -1\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        ret, tmp = 1, 0\n",
    "        for x in map(int, s):\n",
    "            if x > k: return -1\n",
    "            tmp = tmp * 10 + x\n",
    "            if tmp > k:\n",
    "                tmp = x\n",
    "                ret += 1\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        dp = [0] + [inf] * n\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(i-1, -1, -1):\n",
    "                if int(s[j: i]) > k:\n",
    "                    break\n",
    "                dp[i] = min(dp[i], dp[j] + 1)\n",
    "        return dp[-1] if dp[-1] < inf else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        \n",
    "        n = len(s)\n",
    "        dp = [1] * (n+1)\n",
    "        dp[0] = 0\n",
    "        \n",
    "        lenK = len(str(k))\n",
    "        \n",
    "        for j in range(lenK, n+1):  # [1..n]\n",
    "            i = j - lenK + 1\n",
    "            sub_num = int(s[i-1:j])\n",
    "            if sub_num > k:\n",
    "                if lenK == 1:\n",
    "                    return -1\n",
    "                dp[j] = dp[i] + 1\n",
    "            else:\n",
    "                dp[j] = dp[i-1] + 1\n",
    "\n",
    "        print(dp)       \n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        s = ' ' + s\n",
    "        # @cache\n",
    "        # def dfs(u, cnt):\n",
    "        #     if u == 0:\n",
    "        #         return cnt\n",
    "        #     # 分割\n",
    "        #     sm, p = 0, 1\n",
    "        #     res = inf\n",
    "        #     for i in range(u, 0, -1):\n",
    "        #         sm += int(s[i]) * p\n",
    "        #         p *= 10\n",
    "        #         if sm > k:\n",
    "        #             break\n",
    "        #         # 在位置i处进行分割\n",
    "        #         res = min(res, dfs(i - 1, cnt + 1))\n",
    "        #     return res if res != inf else -1\n",
    "        \n",
    "        # return dfs(n - 1, 0)\n",
    "\n",
    "        f = [inf] * (n + 1)\n",
    "        f[0] = 0\n",
    "        for i in range(1, n + 1):\n",
    "            sm, p = 0, 1\n",
    "            for j in range(i, 0, -1):\n",
    "                sm += int(s[j]) * p\n",
    "                p *= 10\n",
    "                if sm > k:\n",
    "                    break\n",
    "                f[i] = min(f[i], f[j - 1] + 1)\n",
    "        print(f)\n",
    "        return f[n] if f[n] != inf else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        m = len(str(k))\n",
    "\n",
    "        # @cache\n",
    "        def dfs(i):\n",
    "            if i < 0: return 0\n",
    "            if i == 0:\n",
    "                return 1\n",
    "\n",
    "            can = []\n",
    "\n",
    "            for j in range(m - 1, -1, -1):\n",
    "                if i - j >= 0 and int(s[i - j:i + 1]) <= k:\n",
    "                    can.append(dfs(i- j - 1) + 1)\n",
    "                    # print(i, j, int(s[i - j:i + 1]))\n",
    "                    break\n",
    "            if len(can) == 0:\n",
    "                raise ValueError()\n",
    "            return min(can)\n",
    "        try:\n",
    "            return dfs(n - 1)\n",
    "        except:\n",
    "            return -1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        m = len(str(k))\n",
    "\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i < 0: return 0\n",
    "            if i == 0:\n",
    "                return 1\n",
    "\n",
    "            can = []\n",
    "\n",
    "            for j in range(m - 1, -1, -1):\n",
    "                if i - j >= 0 and int(s[i - j:i + 1]) <= k:\n",
    "                    return dfs(i- j - 1) + 1\n",
    "                    # can.append(dfs(i- j - 1) + 1)\n",
    "                    # print(i, j, int(s[i - j:i + 1]))\n",
    "                    # break\n",
    "            if len(can) == 0:\n",
    "                raise ValueError()\n",
    "            return min(can)\n",
    "        try:\n",
    "            return dfs(n - 1)\n",
    "        except:\n",
    "            return -1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        m = len(str(k))\n",
    "\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i < 0: return 0\n",
    "            if i == 0:\n",
    "                return 1\n",
    "\n",
    "            can = []\n",
    "\n",
    "            for j in range(0, m):\n",
    "                if i - j >= 0 and int(s[i - j:i + 1]) <= k:\n",
    "                    can.append(dfs(i- j - 1) + 1)\n",
    "            if len(can) == 0:\n",
    "                raise ValueError()\n",
    "            return min(can)\n",
    "        try:\n",
    "            return dfs(n - 1)\n",
    "        except:\n",
    "            return -1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        n= len(s)\n",
    "        t =str(k)\n",
    "        @cache\n",
    "        def dfs(i:int):\n",
    "            if i <0:\n",
    "                return 0\n",
    "            ans =inf \n",
    "            for j in range(max(0,i-len(t)+1),i+1):\n",
    "                if int(s[j:i+1])<=k:\n",
    "                    ans = min(dfs(j-1)+1,ans)\n",
    "            return ans\n",
    "        ans = dfs(n-1)\n",
    "        return -1 if ans ==inf else ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPartition(self, s: str, k: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            ret = inf\n",
    "            for j in range(i-1, -1, -1):\n",
    "                if int(s[j: i]) > k:\n",
    "                    break\n",
    "                ret = min(ret, dfs(j) + 1)\n",
    "            return ret\n",
    "        ret = dfs(len(s))\n",
    "        return ret if ret < inf else -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
